package 面试刷题.小米;

import java.util.Scanner;

public class ch06_LRU缓存 {
    static int maxn = (int) (1e5 + 10);
    // 定义一个 Node 数组，表示手链上的每个珠子（节点）
    static Node[] nodes = new Node[maxn];
    static int n, q;

    /**
     * lru算法，使用双向链表来模拟手链的操作，使用map集合来快速查找珠子。（珠子的值很小所以我用数组代替了（nodes））
     *
     * @param args
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        q = sc.nextInt();

        // 初始化头节点 h 和尾节点 t，h 和 t 是哨兵节点，方便操作
        Node h = new Node(-1);  // 头节点（不属于手链上的珠子）
        Node t = new Node(-1);  // 尾节点（不属于手链上的珠子）
        h.next = t;
        t.pre = h;

        // 初始化手链中的每个珠子，构建一个双向链表
        for (int i = 1; i <= n; i++) {
            Node node = new Node(i);  // 创建第 i 个珠子
            node.pre = t.pre;         // 珠子的 pre 指向尾节点的前一个节点
            node.next = t;            // 珠子的 next 指向尾节点
            t.pre.next = node;        // 尾节点的前一个节点的 next 指向该珠子
            t.pre = node;             // 尾节点的 pre 更新为该珠子
            nodes[i] = node;          // 将珠子存入 nodes 数组
        }

        // 处理 q 次操作
        for (int i = 0; i < q; i++) {
            int a = sc.nextInt();     // 珠子 a 的编号
            int b = sc.nextInt();     // 珠子 b 的编号
            int op = sc.nextInt();    // 操作类型，0 表示将 a 插入到 b 前面，1 表示将 a 插入到 b 后面

            Node nodeA = nodes[a];    // 获取珠子 a 的节点
            Node nodeB = nodes[b];    // 获取珠子 b 的节点

            // 从链表中移除珠子 a
            nodeA.pre.next = nodeA.next; // 珠子 a 的前一个节点的 next 指向珠子 a 的下一个节点
            nodeA.next.pre = nodeA.pre;  // 珠子 a 的下一个节点的 pre 指向珠子 a 的前一个节点

            // 根据 op 的值，选择将珠子 a 插入到 b 的前面或后面
            if (op == 0) {  // 将 a 插入到 b 的前面
                nodeA.next = nodeB;           // 珠子 a 的 next 指向珠子 b
                nodeA.pre = nodeB.pre;        // 珠子 a 的 pre 指向珠子 b 的前一个节点
                nodeB.pre.next = nodeA;       // 珠子 b 的前一个节点的 next 指向珠子 a
                nodeB.pre = nodeA;            // 珠子 b 的 pre 更新为珠子 a
            } else {  // 将 a 插入到 b 的后面
                nodeA.next = nodeB.next;      // 珠子 a 的 next 指向珠子 b 的下一个节点
                nodeA.pre = nodeB;            // 珠子 a 的 pre 指向珠子 b
                nodeB.next.pre = nodeA;       // 珠子 b 的下一个节点的 pre 指向珠子 a
                nodeB.next = nodeA;           // 珠子 b 的 next 更新为珠子 a
            }
        }

        // 输出操作后的手链
        Node curr = h.next;  // 从头节点 h 的下一个节点开始遍历
        while (curr != t) {  // 遍历到尾节点 t 停止
            System.out.print(curr.v + " ");  // 输出当前珠子的编号
            curr = curr.next;                // 移动到下一个珠子
        }
    }

    // 定义双向链表节点类 Node
    static class Node {
        int v;       // 珠子的编号
        Node pre;    // 指向前一个节点的指针
        Node next;   // 指向下一个节点的指针

        // 构造函数，初始化编号 v
        public Node(int v) {
            this.v = v;
        }

        // 构造函数，初始化编号 v 以及前一个节点和下一个节点的指针
        public Node(int v, Node pre, Node next) {
            this.v = v;
            this.pre = pre;
            this.next = next;
        }
    }
}
